package pro.softzhang.algo.lc100;

import com.alibaba.fastjson.JSON;
import pro.softzhang.algo.common.TreeNode;
import pro.softzhang.algo.flag.difficulty.DRed;
import pro.softzhang.algo.flag.x.XOptimal;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 199. 二叉树的右视图
 * https://leetcode.cn/problems/binary-tree-right-side-view/description/
 */
@DRed
public class LC199_BinaryTreeRightSideView {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1, null, new TreeNode(3, null, null));
        List<Integer> result = new Solution().rightSideView(root);
        System.out.println(JSON.toJSONString(result));
    }

    /**
     *
     */
    static
    class Solution {
        public List<Integer> rightSideView(TreeNode root) {
            List<Integer> view = new ArrayList<>();
            if(root == null) {
                return view;
            }

            Queue<TreeNode> q1 = new LinkedList<>(), q2 = new LinkedList<>();
            q1.offer(root);

            while (!q1.isEmpty()) {
                TreeNode node = q1.poll();
                if(node.left != null) {
                    q2.offer(node.left);
                }
                if(node.right != null) {
                    q2.offer(node.right);
                }
                if(q1.isEmpty()) {
                    view.add(node.val);
                    q1 = q2;
                    q2 = new LinkedList<>();
                }
            }
            return view;
        }
    }

    /**
     * 递归实现
     */
    @XOptimal
    static
    class Solution1 {
        public List<Integer> rightSideView(TreeNode root) {
            List<Integer> v = new ArrayList<>();
            dfs(v, root, 0);
            return v;
        }

        private void dfs(List<Integer> v, TreeNode node, int level) {
            if (node == null)
                return;
            if(v.size() == level) {
                v.add(node.val);
            }
            dfs(v, node.right, level + 1);
            dfs(v, node.left, level + 1);
        }
    }
}